package demo9;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-07-26
 * Time: 11:11
 */
public class testRadixSort {

    public static void RadixSort(int[] arr){
        if(arr==null||arr.length<2){
            return ;
        }

        radixSort(arr,0,arr.length-1,maxBit(arr));
    }

    public static int maxBit(int[] arr){
        int max  =0;
        for(int i =0;i<arr.length;++i){
            max = Math.max(arr[i],max);
        }
        int res = 0;
        while(max>0){
            res++;
            max/=10;
        }
        return res;
    }

    public static int getDigit(int x,int d){
        return (x/((int)Math.pow(10,d-1)))%10;
    }

    public static void radixSort(int[] arr,int L,int R,int digit){
        final int radix = 10;
        int[] help = new int[R-L+1];

        for(int d =1 ;d<=digit;++d){//有几位就要进出桶几次

            int[] count = new int[radix];

            for(int i =L;i<=R;++i){
                int j = getDigit(arr[i],d);
                count[j]++;
            }

            //前缀和数组
            for(int i =1;i< radix;++i){
                count[i] = count[i-1] + count[i];
            }

            for(int i = R;i>=L;++i){
                int j = getDigit(arr[i],d);
                help[count[j] -1] = arr[i];
                count[j]--;
            }

            for(int i = L,j=0;i<=R;i++,j++){
                arr[i] = help[j];
            }

        }

    }

    public static void main(String[] args) {

    }

}